Solving sequential games with backward induction

Many games involve simultaneous plays, or at least plays in which a player did not know what strategy the others had followed until after he had made his move. However, many games are sequential, and if a player knows the strategies used by previous players the game is one of perfect information. (Remember that such a game is also one of complete knowledge). Backward induction can be used to solve such games and obtain Nash equilibria. We can illustrate the point by considering the three person Pay-raise Voting Game.

There are three legislators who have to decide how to vote on a pay raise bill. If they vote ‘yes’ they will face popular backlash, with a negative utility of –b. However, if the pay raise is approved, there will be a utility of +p, with b<p. The pay raise bill passes as long as at least two people vote for it. It may be thought that it is best to vote last because then one can see what the other two did, but a tree lets us see that it is not so.

Here the square marked 1 denoted the decision of the first player to vote, those marked 2 the decisions of the second, and so on. The payoffs are given to the right of every branch. For example, in the topmost branch (all vote yes) each has a payoff of p-b; in the branch immediately below it (1 and 2 vote yes and 3 votes no) 1’s and 2’s payoffs are p-b and 3’s payoff is p.

Let us use regressive induction starting with the topmost rightmost square, where player 3 must decide whether to vote yes or no. If she votes yes, her payoff is p-b and if she votes no her payoff is p. Consequently, we may assume that she will vote no and prune the topmost branch. By the same reasoning, we may prune the tree with respect to 3’s decisions (As usual we put an x on the branches which are eliminated). Based on what one may expect 3 to do, 2 makes his decision. For example, on the topmost square marked 2, we may prune off the ‘yes’ branch because by choosing that branch 2’s payoff is p-b while by choosing ‘no’ his payoff is p. The lower decision box for 2 is handled analogously. We are then left with only two branches for 1’s decision; if he votes yes, his expected payoff is p-b, and if he votes no it is p. Hence, he should vote ‘no’ and let the other two who vote after him take the heat. In effect, by voting ‘no’ he forces them to vote ‘yes’ and suffer the voter’s backlash; by contrast, he can claim he voted ‘no’ while getting the raise. One might think that moving last and knowing what the other players have done is always advantageous. However, this is wrong. In many games, though not in all, the player who moves first enjoys a first-mover advantage. Note that no matter what he does, 1 stands to gain as long as the other two aim at the highest payoffs. The strategy set (1 votes no; 2 votes yes; 3 votes yes) is a Nash equilibrium: each player’s strategy is the best possible against those of the other two.

A subgame is any part of a game that remains to be played after a given set of moves. For example, any of the game parts to the right of any box in the Pay-raise Voting Game is a subgame. It turns out that regressive induction allows us to come up not only with a Nash equilibrium, but with a subgame perfect equilibrium, namely an equilibirum that is Nash not only in the whole game, but also in every subgame.

Regressive induction eliminates what are called “incredible threats” from the tree. For example, player 3 may threaten to vote ‘yes’ at the top of the tree, thus choosing p-b instead of p. However, since it is not to her advantage to do so, this threat may be considered non-credible if the game is played once and she aims at maximizing her payoff. Note, however, that if the game is played several times, at some point representatives 2 and 3 should vote ‘no’ in order to avoid being seen as soft touches or, alternatively, they may require that the voting order be rotated periodically.

Powerful as it is, regressive induction in games has some serious practical and theoretical limitations. If either of players 2 and 3 perceive 1’s behavior as unfair, they may engage in retribution even at a disadvantage to themselves, although they know that they will not play with player 1 again; in fact, there is powerful experimental evidence that this is exactly what most of us would do. In short, many people do carry out incredible threats even in one-round games. As using regressive induction with players who do not use it typically fails to maximize one’s expeced payoff, one should know one’s co-players before deciding what strategy to follow.

In addition to the practical problem we just considered, there is an even more serious theoretical one that does not depend on human psychology. Consider the following game, Centipede. Two players, A and B start with $2 each, alternating rounds. On the first round, A can stop the game by stealing $2 from B, or continue the game, in which case he will receive $1 from Nature. Now B can either stop the game by getting $2 from A, or continue, in which case Nature will reward him with $1. The game continues until one of the two players stops or both have $5.

By backward induction, A should stop the game at the first round and pocket $4. However, it would be better if he continued the game until he can get $6 by stopping it at the penultimate round, or, as a second best, until the third round or the end of the game, both with a payoff of $5. The problem is caused by the fact that the payoffs oscillate between high and low, although the general direction is upward. So, although backward induction is unchallenged in decision theory, where the player’s counterpart is incapable of strategic choices, it is far more controversial in sequential game theory, where player engage in strategic decisions.